
//=====================第一   暴力解法 =============================
int strStr(char* haystack, char* needle) {
    int len1 = strlen(haystack);
    int len2 = strlen(needle);

    if(0==len2){    //模式串为空
        return 0;
    }

    for(int i=0;i<=len1-len2;i++){   // 从文本串的左边到右边逐个比较
        int j = 0;
            while(j<len2 && haystack[i+j]==needle[j]){
                j++;
            }

            if(len2==j){
                return i;
            }
    }
    return -1;   // 找不到
}  

// ========================================第二   Rabin-Karp 算法=================================
#include <stdio.h>   // 标准输入输出库
#include <string.h>  // 字符串处理库

#define BASE 256 // 定义字符集大小（ASCII字符集）
#define MOD 101  // 定义质数，用于取模以减少哈希冲突

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack);  // 获取haystack字符串的长度
    int m = strlen(needle);    // 获取needle字符串的长度
    
    if (m == 0) {              // 如果needle是空字符串
        return 0;              // 返回0（空字符串总是匹配）
    }
    if (n < m) {               // 如果haystack比needle短
        return -1;             // 直接返回-1（不可能匹配）
    }
    
    // 计算 BASE^(m-1) % MOD，用于后续滚动哈希计算
    int h = 1;                 // 初始化h为1
    for (int i = 0; i < m - 1; i++) {  // 循环m-1次
        h = (h * BASE) % MOD;  // 每次乘以BASE并取模
    }
    
    // 计算needle的哈希值和haystack第一个窗口的哈希值
    int hash_needle = 0;       // 初始化needle的哈希值
    int hash_window = 0;       // 初始化haystack第一个窗口的哈希值
    for (int i = 0; i < m; i++) {  // 循环m次
        hash_needle = (hash_needle * BASE + needle[i]) % MOD;  // 计算needle哈希值
        hash_window = (hash_window * BASE + haystack[i]) % MOD;  // 计算窗口哈希值
    }
    
    // 滑动窗口遍历haystack
    for (int i = 0; i <= n - m; i++) {  // 遍历所有可能的起始位置
        // 检查当前窗口哈希值是否与needle哈希值匹配
        if (hash_window == hash_needle) {
            // 验证字符串是否真正匹配（防止哈希冲突）
            int j;                       // 声明循环变量
            for (j = 0; j < m; j++) {    // 逐个字符比较
                if (haystack[i + j] != needle[j]) {  // 如果字符不匹配
                    break;               // 跳出循环
                }
            }
            if (j == m) {                // 如果所有字符都匹配
                return i;                // 返回当前起始位置
            }
        }
        
        // 计算下一个窗口的哈希值（如果不是最后一个窗口）
        if (i < n - m) {
            // 使用滚动哈希公式计算下一个窗口的哈希值
            hash_window = (BASE * (hash_window - haystack[i] * h) + haystack[i + m]) % MOD;
            
            // 确保哈希值为正数（避免取模运算导致的负值）
            if (hash_window < 0) {
                hash_window += MOD;      // 加上MOD使其为正
            }
        }
    }
    
    return -1;  // 如果没有找到匹配，返回-1
}


// ========================================第三   KMP 算法=================================
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int strStr(char* haystack, char* needle) {
    int n = strlen(haystack);
    int m = strlen(needle);
    
    if (m == 0) {
        return 0;
    }
    // 构建next数组
    int* next = (int*)malloc(m * sizeof(int));
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < m; i++) {
        while (j > 0 && needle[i] != needle[j]) {
            j = next[j - 1];                      // 回溯 如果遇见不匹配 就回溯，回溯就是说，如果遇见不匹配，就回溯到上一个最长相等后缀的下一个位置
        }
        if (needle[i] == needle[j]) {
            j++;
        }
        next[i] = j;
    }
    
    j = 0;
    for (int i = 0; i < n; i++) {  // 遍历haystack字符串  i 从 0 到 n-1;
        while (j > 0 && haystack[i] != needle[j]) {   // 但是每次遍历，j 不是从0开始，而是从上一个最长相等后缀的下一个位置开始
            j = next[j - 1];
        }
        if (haystack[i] == needle[j]) {
            j++;
        }
        if (j == m) {
            free(next);
            return i - m + 1;
        }
    }
    
    free(next);
    return -1;
}